/**
 *  @license   EPL-2.0
 *  @author	   李东霖
 *  @email	   203981473@qq.com
 *	@purpose   完成常见排序的泛型版本  
 *  @date	   2023-09-05
 */
#pragma once
#include<functional>
#include<iostream>
#include<vector>
#include<stack>
#include<cassert>
/// <summary>
///	包含自定义排序算法的命名空间
/// </summary>
namespace MySort 
{
	/// <summary>
	/// 遍历显示函数
	/// </summary>
	/// <typeparam name="T">参数类型</typeparam>
	/// <param name="arr">显示数组</param>
	/// <param name="length">数组长度</param>
	template<typename T>
	void PrintArr(const T arr[], size_t length)
	{
		for (size_t i = 0; i < length; i++)
		{
			std::cout << arr[i] << "    ";
		}
		std::cout << std::endl;
	}



	/// <summary>
	/// 该类做为所有排序函数的容器
	/// </summary>
			
	template<typename T>
	class Sort final
	{
	public:
		Sort() = default;
		~Sort() = default;


		/// <summary>
		/// 接收可排序的数组 进行冒泡排序 默认升序  稳定排序 原地排序
		/// </summary>
		/// <param name="arr">可排序的数组</param>
		/// <param name="length">可排序的数组长度</param>
		/// <param name="cmp">比较函数 默认升序</param>
		static void BubbSort(T arr[], size_t length, std::function<bool(const T&, const T&)> cmp = Defaultcmp<T>());


		/// <summary>
		/// 接收可排序的数组 进行选择排序 默认升序  不稳定排序 原地排序
		/// </summary>
		/// <param name="arr">可排序的数组</param>
		/// <param name="length">可排序的数组长度</param>
		/// <param name="cmp">比较函数 默认升序</param>
		static void SelectSort(T arr[], size_t length, std::function<bool(const T&, const T&)> cmp = Defaultcmp<T>());


		/// <summary>
		/// 接收可排序的数组 进行插入排序 默认升序  稳定排序 原地排序
		/// </summary>
		/// <param name="arr">可排序的数组</param>
		/// <param name="length">可排序的数组长度</param>
		/// <param name="cmp">比较函数 默认升序</param>
		static void InsertSort(T arr[], size_t length, std::function<bool(const T&, const T&)> cmp = Defaultcmp<T>());

		/// <summary>
		/// 接收可排序的数组 进行希尔排序 默认升序 不稳定排序 原地排序
		/// </summary>
		/// <param name="arr">可排序的数组</param>
		/// <param name="length">可排序的数组长度</param>
		/// <param name="cmp">比较函数 默认升序</param>
		static void ShellSort(T arr[], size_t length, std::function<bool(const T&, const T&)> cmp = Defaultcmp<T>());

		/// <summary>
		/// 接收可排序的数组 进行快速排序 遵循前开后闭原则 默认升序 不稳定排序 原地排序
		/// </summary>
		/// <param name="arr">可排序的数组</param>
		/// <param name="start">可排序的数组头部</param>
		/// <param name="end">可排序的数组尾部</param>
		/// <param name="cmp">比较函数 默认升序</param>
		static void QuickSort(T arr[], size_t start , size_t end, std::function<bool(const T&, const T&)> cmp = Defaultcmp<T>());

		/// <summary>
		/// 接收可排序的数组 进行归并排序 默认升序 稳定排序 非原地排序
		/// </summary>
		/// <param name="arr">可排序的数组</param>
		/// <param name="start">可排序的数组头部</param>
		/// <param name="end">可排序的数组尾部</param>
		/// <param name="cmp">比较函数 默认升序</param>
		static void MergeSort(T arr[], size_t start, size_t end, std::function<bool(const T&, const T&)> cmp = Defaultcmp<T>());

		/// <summary>
		/// 接收可排序的数组 进行堆排序 默认升序 不稳定排序 原地排序
		/// </summary>
		/// <param name="arr">可排序的数组</param>
		/// <param name="length">可排序的数组长度</param>
		/// <param name="cmp">比较函数 默认升序</param>
		static void HeapSort(T arr[], size_t length, std::function<bool(const T&, const T&)> cmp = Defaultcmp<T>());

	private:

		/// <summary>
		/// 模板类的静态长度 传入数组长度 用于追踪显示  
		/// </summary>
		static size_t Length;

		/// <summary>
		/// 交换函数
		/// </summary>
		/// <typeparam name="T"></typeparam>
		/// <param name="lh"></param>
		/// <param name="rh"></param>
		static void Swap(T& lh, T& rh) 
		{
			if (&lh == &rh) return;
			T temp = std::move(rh);
			rh = std::move(lh);
			lh = std::move(temp);
		}

		/// <summary>
		/// 默认匹配仿函数  <
		/// </summary>
		/// <typeparam name="T"></typeparam>
		template<class T>
		class Defaultcmp final 
		{
		public :
			bool operator ()(const T& lh,const T& rh) 
			{
				//assert(lh ||rh);
				return lh < rh;
			}
		};
		
		template <typename T>
		static bool DefaultcmpFunc(const T& lh, const T& rh)
		{
			assert(lh || rh);
			return lh < rh;
		}

		/// <summary>
		/// 快速排序的分区算法  
		/// </summary>
		/// <param name="arr">可排序的数组</param>
		/// <param name="start">可排序的数组分区头部</param>
		/// <param name="end">可排序的数组分区尾部</param>
		/// <param name="cmp">匹配算法 默认升序</param>
		static void Partition(T arr[], int start, int end, std::function<bool(const T&, const T&)> cmp);

		/// <summary>
		/// 归并排序的归并算法  
		/// </summary>
		/// <param name="arr">可排序的数组</param>
		/// <param name="merged">存放有序数组的临时数组</param>
		/// <param name="start">可排序的数组分区头部</param>
		/// <param name="end">可排序的数组分区尾部</param>
		/// <param name="cmp">匹配算法 默认升序</param>
		static void Merge(T arr[], T merged[], int start, int end, std::function<bool(const T&, const T&)> cmp);

		/// <summary>
		/// 堆排序的构建算法
		/// </summary>
		/// <param name="arr">可排序的数组</param>
		/// <param name="start">可排序的数组分区头部</param>
		/// <param name="end">可排序的数组分区尾部</param>
		/// <param name="isAscending">是否是升序排列</param>
		static void Heapify(T arr[], int start, int end, bool isAscending);

	};

	/// <summary>
	/// 模板类的静态长度 传入的数组长度
	/// </summary>
	template<typename T>
	size_t MySort::Sort<T>::Length = 0;

	/// <summary>
	/// 接收可排序的数组 进行冒泡排序 默认升序
	/// </summary>
	/// <param name="arr">可排序的数组</param>
	/// <param name="length">可排序的数组长度</param>
	/// <param name="cmp">比较函数 默认升序</param>
	template<typename T>
	inline void MySort::Sort<T>::BubbSort(T arr[], size_t length, std::function<bool(const T&, const T&)> cmp)
	{
		assert(arr);
		//一个可以提前退出的标志
		bool flag = true;
		for (size_t i = 0; i < length - 1; i++)
		{
			for (size_t j = 0; j < length - 1 - i; j++)
			{
				if (!cmp(arr[j], arr[j + 1]))
				{
					flag = false;
					Swap(arr[j], arr[j + 1]);
				}
			}
			if (flag) break;
			else flag = true;
		}

	}

	/// <summary>
	/// 接收可排序的数组 进行选择排序 默认升序
	/// </summary>
	/// <param name="arr">可排序的数组</param>
	/// <param name="length">可排序的数组长度</param>
	/// <param name="cmp">比较函数 默认升序</param>
	template<typename T>
	inline void Sort<T>::SelectSort(T arr[], size_t length, std::function<bool(const T&, const T&)> cmp)
	{
		assert(arr);
		for (size_t i = 0; i < length; i++)
		{
			size_t index = i;
			for (size_t j = i + 1; j < length; j++)
			{
				if (cmp(arr[j], arr[index])) 
				{
					index = j;
				}
			}
			//发生过交换
			if (index != i) Swap(arr[index], arr[i]);
		}


	}

	/// <summary>
	/// 接收可排序的数组 进行插入排序 默认升序
	/// </summary>
	/// <param name="arr">可排序的数组</param>
	/// <param name="length">可排序的数组长度</param>
	/// <param name="cmp">比较函数 默认升序</param>
	template<typename T>
	inline void Sort<T>::InsertSort(T arr[], size_t length, std::function<bool(const T&, const T&)> cmp)
	{
		assert(arr);
		for (size_t i = 1; i < length; i++)
		{
			T tmp = arr[i];
			int j = i - 1;
			//出来要么走到头，要么是找到一个元素
			while(j >= 0)
			{
				if (cmp(tmp, arr[j])) 
				{
					arr[j + 1] = arr[j];//往后移动
					j--;
				}
				else break;
			}
			//优化 减少没有移动时的赋值
			if (i != j + 1) 
			{
				arr[j + 1] = tmp;
			}
		}

	}


	/// <summary>
	/// 接收可排序的数组 进行希尔排序 默认升序 不稳定排序 原地排序
	/// </summary>
	/// <param name="arr">可排序的数组</param>
	/// <param name="length">可排序的数组长度</param>
	/// <param name="cmp">比较函数 默认升序</param>
	template<typename T>
	inline void Sort<T>::ShellSort(T arr[], size_t length, std::function<bool(const T&, const T&)> cmp)
	{
		assert(arr);
		//定义步长  
		size_t gap = length / 2;
		//步长只要大于0 则进行分组  
		while (gap > 0) 
		{
			for (size_t i = gap; i < length; i++)
			{
				T elem = arr[i];
				int j = i - gap; //步长前
				//进行插入排序
				while (j >= 0) 
				{
					if (cmp(elem, arr[j]))
					{
						arr[j + gap] = arr[j];
						//同一分组的前一个元素
						j -= gap;
					}
					else
					{
						break;
					}
				}
				if (i != j + gap) 
				{
					arr[j + gap] = elem;
				}
			}
			gap = gap / 2;
		}


	}

	/// <summary>
	/// 接收可排序的数组 进行快速排序 遵循前开后闭原则 默认升序 不稳定排序 原地排序
	/// </summary>
	/// <param name="arr">可排序的数组</param>
	/// <param name="start">可排序的数组头部</param>
	/// <param name="end">可排序的数组尾部</param>
	/// <param name="cmp">比较函数 默认升序</param>
	template<typename T>
	inline void Sort<T>::QuickSort(T arr[], size_t start, size_t end, std::function<bool(const T&, const T&)> cmp)
	{
		assert(arr);
		if (start >= end)return;  
		Partition(arr, (int)start, (int)end - 1, cmp);  
	}

	/// <summary>
	/// 快速排序的分区算法  
	/// </summary>
	/// <param name="arr">可排序的数组</param>
	/// <param name="start">可排序的数组分区头部</param>
	/// <param name="end">可排序的数组分区尾部</param>
	/// <param name="cmp">匹配算法 默认升序</param>
	template<typename T>
	inline void MySort::Sort<T>::Partition(T arr[], int start, int end, std::function<bool(const T&, const T&)> cmp)
	{
		if (start >= end) return;
		//设置基准  
		T mid = arr[start];
		//保存范围
		int left = start;
		int right = end;
		//出来必然是基准值的位置 交换 
		while (left < right)
		{
			//右边  
			while (left < right && !cmp(arr[right], mid))
				--right;
			//左边   
			while (left < right && !cmp(mid, arr[left]))
				++left;
			//交换值
			if (left < right) 
				Swap(arr[left], arr[right]);
		}

		//交换基准元素和中间值  
		Swap(arr[start], arr[left]);

		//PrintArr(arr, end - start + 1);
		//递归左边  
		Partition(arr, start, right - 1, cmp);
		//递归右边  
		Partition(arr, left + 1, end, cmp);

		
	}


	/// <summary>
	/// 归并排序的归并算法  
	/// </summary>
	/// <param name="arr">可排序的数组</param>
	/// <param name="merged">存放有序数组的临时数组</param>
	/// <param name="start">可排序的数组分区头部</param>
	/// <param name="end">可排序的数组分区尾部</param>
	/// <param name="cmp">匹配算法 默认升序</param>
	template<typename T>
	inline void Sort<T>::Merge(T arr[],T merged[], int start, int end, std::function<bool(const T&, const T&)> cmp)
	{
		//递归退出条件
		if (start >= end) return;
		size_t mid = start + (end - start) / 2;

		//定义区间 [start,mid],[mid+1,end]
		size_t start1 = start, end1 = mid;  
		size_t start2 = mid + 1, end2 = end;
		//第一步 分治 直到最小不可分   树型结构
		Merge(arr, merged, start1, end1, cmp);
		Merge(arr, merged, start2, end2, cmp);

		//第二步 归并 
		size_t index = start;  
		while (start1 <= end1 && start2 <= end2)
		{
			//确定顺序
			merged[index++] = cmp(arr[start1], arr[start2]) ? arr[start1++] : arr[start2++];
		}
		//处理余下的元素  
		while (start1 <= end1) merged[index++] = arr[start1++];
		while (start2 <= end2) merged[index++] = arr[start2++];

		//查看它排序情况就打开它
		//for (int i = 0; i != Length; ++i) std::cout<<merged[i]<<"	";  printf("\n");
		//将排好序的数组返回来  
		for (int i = start; i <= end; i++)
		{
			arr[i] = merged[i];
		}
	}


	/// <summary>
	/// 接收可排序的数组 进行归并排序 默认升序 稳定排序 非原地排序
	/// </summary>
	/// <param name="arr">可排序的数组</param>
	/// <param name="start">可排序的数组头部</param>
	/// <param name="end">可排序的数组尾部</param>
	/// <param name="cmp">比较函数 默认升序</param>
	template<typename T>
	inline void Sort<T>::MergeSort(T arr[], size_t start, size_t end, std::function<bool(const T&, const T&)> cmp)
	{
		assert(arr);
		Length = end - start;
		//新建一个长度一样的辅助数组
		T* merged = new T[end - start];
		Merge(arr, merged, start, end - 1, cmp);
		delete[] merged;

	}
	
	
	/// <summary>
	/// 接收可排序的数组 进行堆排序 默认升序 不稳定排序 原地排序
	/// </summary>
	/// <param name="arr">可排序的数组</param>
	/// <param name="length">可排序的数组长度</param>
	/// <param name="cmp">比较函数 默认升序</param>
	template<typename T>
	inline void Sort<T>::HeapSort(T arr[], size_t length, std::function<bool(const T&, const T&)> cmp)
	{
		assert(arr);
		
		Length = length;

		//判断是使用大顶堆还是小顶堆 这个堆取决于你传入的cmp算法
		bool isAscending = cmp(1, 2) ? true : false;

		//对于这棵树的每一个非叶子结点都要能够成为一个堆  
		for (int i = (length - 1) / 2; i >= 0; --i)
		{
			Heapify(arr, i, length - 1, isAscending);
		}
		//拿取堆顶元素，并调整结构
		for (size_t i = length - 1; i > 0; --i)
		{
			Swap(arr[0], arr[i]);
			Heapify(arr, 0, i - 1, isAscending);
		}

	}

	/// <summary>
	/// 堆排序的构建算法
	/// </summary>
	/// <param name="arr">可排序的数组</param>
	/// <param name="start">可排序数组分区头部</param>
	/// <param name="end">可排序的数组分区尾部</param>
	/// <param name="isAscending">是否是升序排列</param>
	template<typename T>
	inline void Sort<T>::Heapify(T arr[], int start, int end,bool isAscending)
	{
		//对这个树的每一个非叶子结点都要能够成为一个堆 通过cmp比较确定使用大顶堆还是小顶堆
		int parent = start;
		int child = 2 * start + 1;  //不能比end大，最多等于end。否则不能组成树 先指向左孩子
		if (child > end) return;
		
		// 找出我们需要的子结点
		//存在右孩子 && 通过isAscending比较确定使用大顶堆还是小顶堆 true为小顶堆 false为大顶堆
		if (child + 1 <= end && (isAscending ? (arr[child] > arr[child + 1]) : (arr[child] < arr[child + 1]))) ++child;
		
		//判断满足条件的子结点和父结点的大小是否满足堆结构  满足则不需要修改
		if (isAscending ? (arr[child] > arr[parent]) : (arr[child] < arr[parent])) return;

		//否则更换堆顶元素使其满足条件  
		Swap(arr[child], arr[parent]);
		//递归判断子树是否满足
		Heapify(arr, child, end, isAscending);
		//打印每次调整之后的结果
		//for (size_t i = 0; i < Length; i++) std::cout << arr[i] << "	"; std::cout << std::endl;
	}


#pragma region 失败的搜索函数
/*
/// <summary>
	/// 接收可排序的数组 进行归并排序 默认升序 稳定排序 非原地排序  分治思想
	/// </summary>
	/// <param name="arr">可排序的数组</param>
	/// <param name="length">可排序的数组长度</param>
	/// <param name="cmp">比较函数 默认升序</param>
	template<typename T>
	inline void Sort<T>::MergeSort(T arr[], size_t length, std::function<bool(const T&, const T&)> cmp)
	{
		assert(arr);
		//这里使用迭代来完成

		//初始化
		//std::vector<T > tmpArr; //一个等长的临时数组
		T* tmpArr = new T[length];
		T* arrHead = arr;
		size_t step = 1; //区间分段数
		size_t start; //区间起始位置

		//治 第一步 得到最小区间
		while (step < length)
		{
			//偏移量 分成部分
			int offset = step * 2;
			for (start = 0; start < length; start += offset)
			{
				//将区间分成两等分   [low,mid) [mid,max)
				size_t low = start;
				size_t mid = std::min<size_t>(start + step, length);
				size_t max = std::min<size_t>(start + offset, length);

				//为两个有序数组定义区间
				size_t index = low;
				size_t start1 = low, end1 = mid;
				size_t start2 = mid, end2 = max;

				//第二步 归并
				while (start1 < end1 && start2 < end2)
				{
					//在这里排序
					tmpArr[index++] = cmp(arrHead[start1], arrHead[start2]) ? arrHead[start1++] : arrHead[start2++];
				}
				//处理剩下的部分的数组元素
				while (start1 < end1)tmpArr[index++] = arrHead[start1++];
				while (start2 < end2)tmpArr[index++] = arrHead[start2++];
			}
			//查看它排序情况就打开它
			//for (const T& it : tmpArr)
			//{
			//	std::cout << it << "	";
			//}
			//std::cout << std::endl;

			//交换排序数组和未排序数组 tmpArr是排过一次序的
			//使用移动语义交换控制权
			Swap(*arrHead, *tmpArr);

			//开始下一次
			step *= 2;
		}
		//因为我们不知道他需要匹配多少次，如果有序的不是传入arr数组，那么我们就拷贝一份
		if (arr != arrHead)
		{
			memmove(arr, arrHead, length * sizeof(T));
			tmpArr = arrHead;
		}
		free(tmpArr);
	}
*/
#pragma endregion


	










}